package app.champaign;

public class dp_demo{

    public static void main(String[] args) {
        int[] A = {2, 5 ,7};
        int M = 27;
        int i = coinChange(A, M);
        System.out.println(i);
    }

    
    public static int coinChange2(int A[], int M){
        
        //开辟一个数组，一维
        int[] f = new int[M + 1];
        //硬币的种类
        int n = A.length;

        f[0] = 0;

        for(int i = 0; i <= M; i++){
            f[i] = Integer.MAX_VALUE;//假设每次的初始结果是拼不出来的
            for(int j = 0; j < n; j++){
                if(i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE){
                    f[i] = Math.min(f[i - A[j]] + 1, f[i]);
                }
            }
        }
        if(f[M] == Integer.MAX_VALUE){
            f[M] = -1;
        }
        return f[M];
    }

                                            //{2,5,7}  //27
    public static int coinChange(int[] A, int M){
        //数组开多大
        //0...n: [n+1]
        //0...n-1: [n]
        int [] f =new int[M + 1];
        int n = A.length; // numbers of kinds of coins

        //initialization
        f[0] = 0;

        int i, j;
        // f[1], f[2], ... f[27]
        for (i = 1; i <= M; i++) {
            f[i] = Integer.MAX_VALUE; //首先把f[i]设置到最大值，假设它拼不出来，有变化再更改
            //last coin A[j]
            for(j = 0; j < n; j++){
                if(i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE){
                    f[i] =  Math.min(f[i - A[j]] + 1, f[i]);
                }
               
            }
        }

        if(f[M] == Integer.MAX_VALUE){
            f[M] = -1;
        }
        return f[M];
    }

}